package com.love.labuladong.monotonicqueue;

import java.util.Arrays;

/**
 * @Author : zh
 * @Description : 239. 滑动窗口最大值
 * @Date : 2024-09-20 09:03
 */
public class MaxSlidingWindow239 {

    static int MAXN = 100001;

    // 简单的队列 [左大右小的单调队列]
    static int[] queue = new int[MAXN];

    static int h = 0,t = 0;

    public static int[] maxSlidingWindow(int[] nums, int k) {
        // queue 里面放 nums 的下标
        for (int i = 0; i < k -1; i++) {
            // h < t 表示 queue 里面有数据
            // nums[queue[t-1]] <= nums[i] ： 队列最右边的下标对应的数值是否小于等于当前 nums[i]
            while (h < t && nums[queue[t-1]] <= nums[i]){
                // 相当于弹出queue最右边的数字
                t--;
            }
            //将当前 i 从 queue 最右边加入, 能经过上面 while，则表明该queue形成，左大右小的单调队列
            queue[t++] = i;
        }
        // 既是答案的个数，也是 l 的边界条件
        int  end = nums.length - k + 1;
        int[] ans = new int[end];
        for (int l = 0,r = k -1; l < end; l++,r++){
            while (h < t && nums[queue[t-1]] <= nums[r]){
                t--;
            }
            queue[t++] = r;
            // 收集当前窗口答案
            ans[l] = nums[queue[h]];
            // queue[h] 即为当前窗口的最大值，窗口即将向移动，如果 queue[h] 刚好是窗口的最左边的数字，
            // 那窗口向右滑动，queue[h]超出范围了，也得把它从左边弹出去
            if(queue[h] == l){
                h++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int[] ans = maxSlidingWindow(nums,3);
        System.out.println(Arrays.toString(ans));

    }


}
